package com.fjl.list.leetcode378;

import java.util.PriorityQueue;

/**
 * @Description
 * @Author: 01195
 * @Date: 2025/2/19 14:30
 */
public class FindKthSmallest {

    //给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
    //请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。
    //
    //你必须找到一个内存复杂度优于 O(n2) 的解决方案。
    public static void main(String[] args) {

    }
    //这道题其实是前文 单链表的六大解题套路 中讲过的 23. 合并K个升序链表 的变体。
    //
    //矩阵中的每一行都是排好序的，就好比多条有序链表，你用优先级队列施展合并多条有序链表的逻辑就能找到第 k 小的元素了。
    public int kthSmallest(int[][] matrix, int k) {
        // 存储二元组 (matrix[i][j], i, j)
        // i, j 记录当前元素的索引位置，用于生成下一个节点
        PriorityQueue<int[]> queue = new PriorityQueue<>(
                (a, b) -> {
                    return a[0] - b[0];
                });
        // 初始化优先级队列，把每一行的第一个元素装进去
        for (int i = 0; i < matrix[0].length; i++) {
            queue.add(new int[]{matrix[i][0], i, 0});
        }
        int value = -1;
        // 执行合并多个有序链表的逻辑，找到第 k 小的元素
        while (!queue.isEmpty() && k > 0) {
            int[] poll = queue.poll();
            value = poll[0];
            k--;
            int i = poll[1];
            int j = poll[2];
            // 链表中的下一个节点加入优先级队列
            if (j + 1 < matrix[i].length) {
                queue.add(new int[]{matrix[i][j + 1], i, j + 1});
            }
        }
        return value;
    }
}
